English+GermanWikipedia - /page/entry.mu

<!DOCTYPE html>

<title>Verteilte Hashtabelle</title>

</head>

<h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">Verteilte Hashtabelle</span></h1>

</header>

</div>

<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="de" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="de" dir="ltr"><p>Eine <b>verteilte Hashtabelle</b> (<span style="font-style:normal;font-weight:normal"><a href="Englische_Sprache" title="Englische Sprache">englisch</a></span> <span lang="en-Latn" style="font-style:italic">distributed hash table</span>, DHT) ist eine <a href="Datenstruktur" title="Datenstruktur">Datenstruktur</a>, die beispielsweise verwendet wird, um den Speicherplatz einer Datei in einem <a href="Peer-to-Peer" title="Peer-to-Peer">P2P-System</a> effizient zu verteilen.

</p><p>Die Daten werden möglichst gleichmäßig über die vorhandenen Speicherknoten verteilt. Jeder Speicherknoten entspricht dabei einem Eintrag in der <a href="Hashtabelle" title="Hashtabelle">Hashtabelle</a>. Die selbstorganisierende Datenstruktur kann den Ausfall, Beitritt und Austritt von Knoten abbilden. Die Grundlage für verteilte Hashtabellen bilden <a href="Konsistente_Hashfunktion" title="Konsistente Hashfunktion">konsistente Hash-Funktionen</a>.

</p><p>Man unterscheidet DHTs nach dem Speicherschema. Die Daten können direkt innerhalb der DHT abgelegt werden (direct storage) oder in der DHT kann ein Verweis auf die Daten vorgehalten werden (indirect storage). Direct Storage bietet sich nur für kleine Daten (< 1 kB) an, da sonst das System zu unflexibel werden würde.

</p>

<div class="mw-heading mw-heading2"><h2 id="Eigenschaften">Eigenschaften</h2></div>

<p>Eigenschaften von DHTs sind:

</p>

<ul><li><a href="Hardware-Fehlertoleranz" title="Hardware-Fehlertoleranz">Fehlertoleranz</a>: Das System sollte zuverlässig funktionieren, auch wenn Knoten ausfallen oder das System verlassen.</li>

<li><a href="Lastverteilung_(Informatik)" title="Lastverteilung (Informatik)">Lastenverteilung</a>: Schlüssel werden gleichmäßig auf alle Knoten verteilt.</li>

<li><a href="Robustheit" title="Robustheit">Robustheit</a>: Das System sollte „korrekt“ funktionieren können, auch wenn ein Teil (möglicherweise ein Großteil) der Knoten versucht, das System zu stören.</li>

<li><a href="Selbstorganisation" title="Selbstorganisation">Selbstorganisation</a>: Es ist keine manuelle Konfiguration nötig.</li>

<li><a href="Skalierbarkeit" title="Skalierbarkeit">Skalierbarkeit</a>: Das System sollte in der Lage sein, auch mit einer großen Anzahl von Knoten funktionsfähig zu bleiben.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Prinzipielle_Arbeitsweise">Prinzipielle Arbeitsweise</h2></div>

<p>Mittels einer <a href="Hashfunktion" title="Hashfunktion">Hashfunktion</a> werden den Datenobjekten <a href="Nummerung" title="Nummerung">Schlüssel</a> in einem <a href="Linearit%C3%A4t_(Mathematik)" title="Linearität (Mathematik)">linearen</a> <a href="Zielmenge" title="Zielmenge">Wertebereich</a> vergeben, welcher möglichst gleichmäßig über die Knoten der Knotenmenge verteilt wird. Für jeden Teilbereich des Schlüsselraumes ist dabei mindestens ein Knoten zuständig. Oft sind jedoch auch mehrere Knoten für denselben Bereich verantwortlich, wobei sich die Zuständigkeiten dynamisch ändern. Ein <a href="Kommunikationsprotokoll" title="Kommunikationsprotokoll">Beitrittsprotokoll</a> regelt die Aufnahme neuer Knoten in das existierende System. Das Protokoll stellt dann die Verbindungen zu den <i>Nachbarknoten</i> her und regelt üblicherweise auch die Konstruktion von <a href="Routingtabelle" title="Routingtabelle">Routingtabellen</a>.

</p><p>Die Routingtabellen werden von den DHT-Knoten zur Ermittlung anderer Knoten benutzt, die für bestimmte Datensätze zuständig sind. Die Definition der „Entfernung“ ist dabei mit der Struktur und der <a href="Topologie_(Rechnernetz)" title="Topologie (Rechnernetz)">Topologie</a> verbunden und variiert in unterschiedlichen Systemen. Sie muss nicht zwingend mit der physischen Organisation der Knoten übereinstimmen. Eine verteilte Hashtabelle, die ihre Knoten in einem <a href="Euklidischer_Raum" title="Euklidischer Raum">euklidischen Raum</a> platziert, könnte den Knoten mit dem geringsten <a href="Euklidischer_Abstand" title="Euklidischer Abstand">euklidischen Abstand</a> zu einem Schlüssel wählen. Die Routingtabellen sollen es jedem Knoten erlauben, den nächsten Knoten zu einem Schlüssel in <a href="Landau-Symbole" title="Landau-Symbole"><i>O</i>(log <i>n</i>)</a> Suchschritten zu erreichen.

</p><p>Durch eine generische Schnittstelle, die nur zwei Funktionen <code>publish(Schlüssel, Inhalt)</code> und <code>lookup(Schlüssel)</code> anbietet, lassen sich die implementierten Algorithmen auswechseln.

</p>

<div class="mw-heading mw-heading2"><h2 id="Partitionierung_des_Schlüsselraums"><span id="Partitionierung_des_Schl.C3.BCsselraums"></span>Partitionierung des Schlüsselraums</h2></div>

<p>Bei den meisten DHTs geschieht die Abbildung von Schlüsseln auf Knoten mittels einer Variante von <a href="Konsistente_Hashfunktion" title="Konsistente Hashfunktion">konsistentem Hashing</a> oder Rendezvouz-Hashing. Diese beiden Varianten wurden wohl gleichzeitig, aber unabhängig entwickelt, um das DHT-Problem zu lösen.

</p><p>Sowohl konsistentes Hashing als auch Rendezvouz-Hashing haben die grundlegende Eigenschaft, dass sich bei Beitritt oder Austritt eines Knotens nur die Schlüssel der benachbarten Knoten ändern und alle anderen Knoten nicht beeinträchtigt werden. In konventionellen <a href="Hashtabelle" title="Hashtabelle">Hashtabellen</a> hingegen wird bei hinzufügen oder entfernen eines Buckets fast der vollständige Schlüsselbereich neu verteilt. Wenn sich die Zuständigkeit von Datenobjekten ändert, ist eine Daten-Umverteilung notwendig. Diese belastet das Netzwerk und die Datenbandbreite. Deshalb werden DHTs so gestaltet, dass sie auch häufige Ein- und Austritte von Knoten effizient unterstützen können.

</p>

<div class="mw-heading mw-heading3"><h3 id="Konsistentes_Hashing">Konsistentes Hashing</h3></div>

<p>Beim konsistenten Hashing wird eine Distanzfunktion <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \delta (k_{1},k_{2})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \delta (k_{1},k_{2})}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/393b0b9cbab3983c701a045715c4390cb84f31dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.423ex; height:2.843ex;" alt="{\displaystyle \delta (k_{1},k_{2})}" loading="lazy"></span> verwendet. Diese gibt die Distanz zwischen zwei Schlüsseln <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k_{1}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/376315fd4983f01dada5ec2f7bebc48455b14a66.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.265ex; height:2.509ex;" alt="{\displaystyle k_{1}}" loading="lazy"></span> und <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k_{2}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c51b4ba57ee596d8435fc4ed76703ca3a2fc444a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.265ex; height:2.509ex;" alt="{\displaystyle k_{2}}" loading="lazy"></span> an. Die Distanz ist dabei unabhängig von der geographischen Distanz oder der Latenz im Netzwerk. Außerdem erhält jeder Knoten <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"></span> des Netzwerks einen Schlüssel, welchen wir seinen Identifikator <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i_{x}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i_{x}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/6ba704d71ac5022a9bda478a8ee8010557700974.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.975ex; height:2.509ex;" alt="{\displaystyle i_{x}}" loading="lazy"></span> (ID von Knoten <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"></span>) nennen. Jeder Knoten ist dann für die Speicherung derer Elemente zuständig, deren Distanz zu seiner ID am geringsten ist: <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x=\operatorname {argmin} _{y}\delta (k,i_{y})}">

<msub>

<mi>argmin</mi>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x=\operatorname {argmin} _{y}\delta (k,i_{y})}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/3d8c34a45ebecde35115c18db2ef848cad3c2d64.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:19.931ex; height:3.176ex;" alt="{\displaystyle x=\operatorname {argmin} _{y}\delta (k,i_{y})}" loading="lazy"></span>.

</p><p>Beispielsweise setzt Chord konsistentes Hashing ein, wobei die Knoten als Punkte auf einem Kreis und <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \delta (k_{1},k_{2})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \delta (k_{1},k_{2})}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/393b0b9cbab3983c701a045715c4390cb84f31dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.423ex; height:2.843ex;" alt="{\displaystyle \delta (k_{1},k_{2})}" loading="lazy"></span> als der Kreisbogen von  <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k_{1}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/376315fd4983f01dada5ec2f7bebc48455b14a66.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.265ex; height:2.509ex;" alt="{\displaystyle k_{1}}" loading="lazy"></span> nach <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k_{2}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c51b4ba57ee596d8435fc4ed76703ca3a2fc444a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.265ex; height:2.509ex;" alt="{\displaystyle k_{2}}" loading="lazy"></span> im Uhrzeigersinn aufgefasst werden. Der kreisförmige Schlüsselraum besteht also aus zusammenhängenden Segmenten, deren Endpunkte die Knoten-IDs sind. Wenn also zum Beispiel <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i_{1}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/5484b6123d92ccfcef3204a32720eeae60998e29.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.857ex; height:2.509ex;" alt="{\displaystyle i_{1}}" loading="lazy"></span> und <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i_{2}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/14feff7997a635a64f7dfacfbd0374a24ab279bd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.857ex; height:2.509ex;" alt="{\displaystyle i_{2}}" loading="lazy"></span> zwei im Kreis aufeinander folgende Knoten-IDs sind, dann ist der Knoten <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i_{1}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/5484b6123d92ccfcef3204a32720eeae60998e29.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.857ex; height:2.509ex;" alt="{\displaystyle i_{1}}" loading="lazy"></span> für alle Schlüssel zwischen <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i_{1}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/5484b6123d92ccfcef3204a32720eeae60998e29.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.857ex; height:2.509ex;" alt="{\displaystyle i_{1}}" loading="lazy"></span> und <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i_{2}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/14feff7997a635a64f7dfacfbd0374a24ab279bd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.857ex; height:2.509ex;" alt="{\displaystyle i_{2}}" loading="lazy"></span> zuständig.

</p>

<div class="mw-heading mw-heading3"><h3 id="Rendezvous-Hashing">Rendezvous-Hashing</h3></div>

<p>Beim Rendezvouz-Hashing benutzen alle Clients, welche einen Schlüssel auf einen der <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"></span> Knoten abbilden wollen, die gleiche, zu Beginn gewählte Hashfunktion <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h()}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h()}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/992946ab39fbae54bdf55bfa775e9a19d97205e2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.148ex; height:2.843ex;" alt="{\displaystyle h()}" loading="lazy"></span>. Außerdem haben alle Clients die gleiche Liste von IDs <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{S_{1},S_{2},...,S_{n}\}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{S_{1},S_{2},...,S_{n}\}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ea02affe014cad9bba1a24b792536c99e0a9bcfd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.13ex; height:2.843ex;" alt="{\displaystyle \{S_{1},S_{2},...,S_{n}\}}" loading="lazy"></span>, eine für jeden Knoten. Um den richtigen Knoten für einen Schlüssel <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"></span> zu bestimmen, werden zunächst <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"></span> Hash-Gewichte <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w_{1}=h(S_{1},k),\ w_{2}=h(S_{2},k),\ ...,\ w_{n}=h(S_{n},k)}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w_{1}=h(S_{1},k),\ w_{2}=h(S_{2},k),\ ...,\ w_{n}=h(S_{n},k)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/607de7a8e68d7c378205095b2d81d6c238cd4db7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:49.342ex; height:2.843ex;" alt="{\displaystyle w_{1}=h(S_{1},k),\ w_{2}=h(S_{2},k),\ ...,\ w_{n}=h(S_{n},k)}" loading="lazy"></span> berechnet. Der Schlüssel wird dann mit dem dem Maximum dieser Werte entsprechenden Knoten assoziiert. Ein Knoten mit ID <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S_{x}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S_{x}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e17297f0fdd502bf3cf9e999b890ffb872869c82.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.597ex; height:2.509ex;" alt="{\displaystyle S_{x}}" loading="lazy"></span> ist also für alle Schlüssel <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k_{m}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k_{m}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/25d16171af1c8efc54dfb43a8c83893cf7516f01.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.886ex; height:2.509ex;" alt="{\displaystyle k_{m}}" loading="lazy"></span> zuständig, deren Hash-Gewicht <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h(S_{x},k_{m})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h(S_{x},k_{m})}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/6c9d066cc97a7ab7823119933d5968e5d1eb21e8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.666ex; height:2.843ex;" alt="{\displaystyle h(S_{x},k_{m})}" loading="lazy"></span> höher als die Hash-Gewichte aller anderen Knoten für den Schlüssel ist.

</p>

<div class="mw-heading mw-heading3"><h3 id="Lokalitätserhaltendes_Hashing"><span id="Lokalit.C3.A4tserhaltendes_Hashing"></span>Lokalitätserhaltendes Hashing</h3></div>

<p>Lokalitätserhaltendes Hashing stellt sicher, dass ähnliche Schlüssel auch ähnlichen Knoten zugeteilt werden. Dadurch können effizientere Range Queries ermöglicht werden. Dabei kann es allerdings vorkommen, dass die Verteilung des Schlüsselraums auf die Knoten und damit deren Auslastung nicht mehr uniform zufällig ist. Das Framework Self-Chord zum Beispiel macht Objektschlüssel von Knoten-IDs unabhängig und sortiert Schlüssel entlang eines Ringspeichers mit Hilfe eines statistischen Ansatzes, der auf dem <a href="Schwarmintelligenz" class="mw-redirect" title="Schwarmintelligenz">Schwarmintelligenz-Paradigma</a> beruht.<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> Das Sortieren stellt sicher, dass benachbarte Knoten für ähnliche Schlüssel zuständig sind und Abfragen wie z. B. Range Queries so in logarithmischer Zeit ausgeführt werden können.

</p>

<div class="mw-heading mw-heading2"><h2 id="Overlay-Netz">Overlay-Netz</h2></div>

<p>Das <a href="Overlay-Netz" title="Overlay-Netz">Overlay-Netz</a> verbindet die Knoten, sodass diese den jeweiligen zuständigen Knoten für Schlüssel finden können. Dabei hält jeder Knoten in einer <a href="Routingtabelle" title="Routingtabelle">Routingtabelle</a> Verbindungen zu anderen Knoten (seinen Nachbarn). Ein Knoten wählt seine Nachbarn entsprechend der <a href="Netzwerktopologie" class="mw-redirect" title="Netzwerktopologie">Netzwerktopologie</a> (Struktur des Netzwerks).

</p><p>Alle DHT-Topologien verbindet eine grundlegende Eigenschaft: für jeden Schlüssel <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"></span> weiß jeder Knoten entweder die ID des Knotens, der für <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"></span> zuständig ist, oder er hat einen Link zu einem Knoten, dessen ID näher an <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"></span> ist, definiert durch ein Distanzmaß in Abschnitt Partitionierung des Schlüsselraums. Eine Nachricht kann dann einfach an den zuständigen Knoten von <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"></span> geroutet werden: Bei jedem Schritt wird die Nachricht an denjenigen Knoten weitergeleitet, dessen ID <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"></span> am nächsten ist, bis der zuständige Knoten erreicht wird. Dieser Algorithmus ist im Allgemeinen nicht global optimal. Manchmal wird dieses Verfahren Schlüssel-basiertes Routing genannt.

</p><p>Das Overlay-Netz hat zwei Parameter, welche einen großen Einfluss auf seine Leistung haben. Die maximale Routenlänge sollte klein sein, damit Pakete schnell ankommen, und der maximale Knotengrad sollte klein sein, damit der Overhead pro besuchtem Knoten klein ist. Dabei stehen die beiden Parameter in einem Tradeoff-Verhältnis. Einige typische Verhältnisse sind in der folgenden Tabelle beschrieben.

</p>

<th>Max. Knotengrad</th>

<th>Max. Routenlänge</th>

<th>Benutzt in</th>

<th>Bemerkung

</th></tr>

<tr>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(1)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e66384bc40452c5452f33563fe0e27e803b0cc21.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.745ex; height:2.843ex;" alt="{\displaystyle O(1)}" loading="lazy"></span></td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/34109fe397fdcff370079185bfdb65826cb5565a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.977ex; height:2.843ex;" alt="{\displaystyle O(n)}" loading="lazy"></span></td>

<td>Schlechtestmögliche Routenlänge, Anfragen werden sehr langsam

</td></tr>

<tr>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(\log n)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/aae0f22048ba6b7c05dbae17b056bfa16e21807d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.336ex; height:2.843ex;" alt="{\displaystyle O(\log n)}" loading="lazy"></span></td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(\log n)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/aae0f22048ba6b7c05dbae17b056bfa16e21807d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.336ex; height:2.843ex;" alt="{\displaystyle O(\log n)}" loading="lazy"></span></td>

<td>Chord <br> <a href="Kademlia" title="Kademlia">Kademlia</a> <br> Pastry <br> Tapestry</td>

<td>Am verbreitetsten aber nicht optimal (Nachbargrad/Routenlänge-Verhältnis). Chord ist die einfachste Version, Kademlia scheint die beliebteste optimierte Variante zu sein (sollte verbesserte durschn. Zeit für Anfragen haben)

</td></tr>

<tr>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(\log n)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/aae0f22048ba6b7c05dbae17b056bfa16e21807d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.336ex; height:2.843ex;" alt="{\displaystyle O(\log n)}" loading="lazy"></span></td>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(\log n/\log(\log n))}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/8250f6f4e5502e5b4045dac638b5b99b815e2fbe.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:19.42ex; height:2.843ex;" alt="{\displaystyle O(\log n/\log(\log n))}" loading="lazy"></span></td>

<td>Koorde</td>

<td>

<p>Wohl komplexere Implementierung aber Anfragen können schneller sein (niedrigere Worst-Case-Schranke)

</p>

</td></tr>

<tr>

<msqrt>

</msqrt>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O({\sqrt {n}})}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f5526ab1252c0f682bbe07c0ad67c0f29de5522b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:6.913ex; height:3.009ex;" alt="{\displaystyle O({\sqrt {n}})}" loading="lazy"></span></td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(1)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e66384bc40452c5452f33563fe0e27e803b0cc21.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.745ex; height:2.843ex;" alt="{\displaystyle O(1)}" loading="lazy"></span></td>

<td>

<p>Höchste lokale Speicherplatzanforderungen, hohe Kommunikationslast nach Beitritt und Austritt eines Knotens

</p>

</td></tr></tbody></table>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(\log n)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/aae0f22048ba6b7c05dbae17b056bfa16e21807d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.336ex; height:2.843ex;" alt="{\displaystyle O(\log n)}" loading="lazy"></span> als maximaler Nachbargrad und maximale Routenlänge ist die am weitesten verbreitete Parametrisierung. Obwohl der Nachbargrad/Routenlänge-Tradeoff bei ihr nicht optimal ist, ermöglicht sie oft eine höhere Flexibilität bei der Wahl der Nachbarn. Viele DHTs nutzen diese Flexibilität, um Nachbarn mit möglichst geringer Latenz im darunterliegenden physikalischen Netzwerk auszuwählen. Im Allgemeinen erstellen DHTs navigierbare kleine-Welt-Netzwerk-Topologien mit dem Tradeoff zwischen Routenlänge und Netzwerkgrad<sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup>.

</p><p>Die maximale Routenlänge ist eng verwandt mit dem <a href="Durchmesser_(Graphentheorie)" class="mw-redirect" title="Durchmesser (Graphentheorie)">Durchmesser</a> (des Netzwerks): der maximalen Anzahl Hops in einem beliebigen kürzesten Pfad zwischen zwei Knoten. Die Worst-Case-Routenlänge des Netzwerks ist offensichtlich mindestens so groß wie der Durchmesser, folglich haben DHTs die in der <a href="Graphentheorie" title="Graphentheorie">Graphentheorie</a> fundamentale Limitierung des Knotengrad/Durchmesser-Tradeoffs<sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup>. Die Routenlänge kann auch größer als der Durchmesser sein, da der greedy Routingalgorithmus kürzeste Pfade eventuell nicht findet<sup id="cite_ref-4" class="reference"><a href="#cite_note-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup>.

</p>

<div class="mw-heading mw-heading3"><h3 id="Algorithmen_für_Overlay-Netze"><span id="Algorithmen_f.C3.BCr_Overlay-Netze"></span>Algorithmen für Overlay-Netze</h3></div>

<p>Neben Routing gibt es viele Algorithmen, welche die Struktur von Overlay-Netzen in DHTs ausnutzen, um Nachrichten an alle Knoten oder eine Teilmenge zu senden.<sup id="cite_ref-5" class="reference"><a href="#cite_note-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup> Diese Algorithmen werden von Anwendungen für Overlay-Multicasts, Range Queries oder zum Sammeln von Statistiken eingesetzt. Zwei auf diesem Ansatz basierende Systeme sind Structella<sup id="cite_ref-6" class="reference"><a href="#cite_note-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup>, das Flooding und Random Walks auf einem Pastry-Overlay implementiert, sowie DQ-DHT, das einen dynamischen Query-Suchalgorithmus über einem Chord-Netzwerk implementiert.<sup id="cite_ref-7" class="reference"><a href="#cite_note-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="Implementierungen">Implementierungen</h2></div>

<p>Auf vielen Rechnern ist das Senden von Nachrichten deutlich teurer als lokale Hashtabellen-Zugriffe. Deshalb ist eine Bündelung vieler Nachrichten in einen Batch sinnvoll. Die Nachrichten werden unter der Annahme, dass jeder Knoten einen lokalen Batch von maximal <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f11423fbb2e967f986e36804a8ae4271734917c3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.998ex; height:2.176ex;" alt="{\displaystyle b}" loading="lazy"></span> Nachrichten hat, wie folgt gebündelt. Jeder Knoten sortiert seinen lokalen Batch zunächst nach der ID des für die Nachricht zuständigen Knotens. Dies ist in <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(b+n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(b+n)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/bbe312649e12f6a3f075a5d50f4d6ae2455be577.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.815ex; height:2.843ex;" alt="{\displaystyle O(b+n)}" loading="lazy"></span> Zeit mit <a href="Bucketsort" title="Bucketsort">Bucketsort</a> möglich, wobei <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"></span> die Knotenanzahl in der DHT ist. Falls es in einem Batch mehrere Operationen für denselben Key gibt, wird der Batch noch vor dem Senden reduziert. Zum Beispiel können mehrere Anfragen für denselben Key zu einer reduziert werden oder mehrere inkrement-Operationen zu einer add-Operation. Dies kann mit einer lokalen Hashtable realisiert werden. Schließlich werden die Operationen an die jeweiligen Knoten geschickt.<sup id="cite_ref-8" class="reference"><a href="#cite_note-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup>

</p><p>Derzeit existieren unter anderem folgende Implementierungen verteilter Hashtabellen:

</p>

<li><a href="Kademlia" title="Kademlia">Kademlia</a> – Strukturen basierend auf diesem Algorithmus existieren in mehreren P2P-Netzwerken, sind allerdings meist nicht untereinander kompatibel. Implementierungen:

<ul><li>KAD – Entwicklung des <a href="EMule" title="EMule">eMule</a>-Entwicklungsteams, basierend auf dem Kademlia-Algorithmus, um die mit der Zeit ausfallenden Server des <a href="EDonkey2000" title="EDonkey2000">eDonkey2000</a>-Netzwerks zu ersetzen.</li>

<li>Mojito – Entwicklung des <a href="LimeWire" title="LimeWire">LimeWire</a>-Entwicklungsteams zur schnellen Quellenermittlung innerhalb des <a href="Gnutella" title="Gnutella">Gnutella</a>-Netzwerks.</li></ul></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Anwendungen">Anwendungen</h2></div>

<div class="mw-heading mw-heading3"><h3 id="DHTs_zur_Datenspeicherung">DHTs zur Datenspeicherung</h3></div>

<ul><li><a rel="nofollow" class="external text" href="https://github.com/savoirfairelinux/opendht">OpenDHT</a></li>

<li><a rel="nofollow" class="external text" href="http://www.bamboo-dht.org/">Bamboo</a></li>

<li><a rel="nofollow" class="external text" href="http://www.pdos.lcs.mit.edu/chord/">The Chord/DHash Project</a></li>

<li><a rel="nofollow" class="external text" href="http://www.freepastry.org/">FreePastry</a></li>

<div class="mw-heading mw-heading3"><h3 id="Software">Software</h3></div>

<ul><li>apt-p2p (<a href="Paketverwaltung" title="Paketverwaltung">Paketverwaltungssystem</a>): Verteiltes Update auf Basis von <a href="Advanced_Packaging_Tool" title="Advanced Packaging Tool">apt</a></li>

<li><a href="Vuze" title="Vuze">Vuze</a>: <a href="BitTorrent" title="BitTorrent">BitTorrent</a>-Client</li>

<li><a href="BitComet" title="BitComet">BitComet</a>: <a href="BitTorrent" title="BitTorrent">BitTorrent</a>-Client</li>

<li><a href="BitTorrent_(Client)" title="BitTorrent (Client)">BitTorrent</a> (ab Version 4.1.0)</li>

<li><a href="Coral_(Netzwerk)" title="Coral (Netzwerk)">Coral</a>: Verteilungsnetzwerk für Inhalte</li>

<li><a href="CSpace" title="CSpace">CSpace</a>: Instant Messenger mit Kademlia</li>

<li><a href="Deluge" title="Deluge">Deluge</a> (BitTorrent-Client)</li>

<li><a href="EDonkey2000" title="EDonkey2000">eDonkey2000</a>, Name: <a href="Overnet" title="Overnet">Overnet</a></li>

<li><a href="EMule" title="EMule">eMule</a> (ab Version 0.40) und <a href="AMule" title="AMule">aMule</a> (ab Version 2.1.0), Name: Kad</li>

<li><a href="Free_Download_Manager" title="Free Download Manager">Free Download Manager</a>: freier <a href="Download-Manager" title="Download-Manager">Download-Manager</a>, der auch <a href="BitTorrent" title="BitTorrent">BitTorrent</a> und DHT beherrscht</li>

<li><a href="Hyphanet_(Software)" title="Hyphanet (Software)">Freenet</a>: Anonymer <a href="Datenspeicher" title="Datenspeicher">Datenspeicher</a>.</li>

<li>Halite: <a href="BitTorrent" title="BitTorrent">BitTorrent</a>-Client</li>

<li><a href="KTorrent" title="KTorrent">KTorrent</a>: <a href="BitTorrent" title="BitTorrent">BitTorrent</a>-Client</li>

<li><a href="LimeWire" title="LimeWire">LimeWire</a> (Name: Mojito)</li>

<li><a href="MLDonkey" title="MLDonkey">MLDonkey</a> (Overnet und Kademlia)</li>

<li><a href="%CE%9CTorrent" title="ΜTorrent">µTorrent</a>: <a href="BitTorrent" title="BitTorrent">BitTorrent</a>-Client</li>

<li><a href="QBittorrent" title="QBittorrent">qBittorrent</a>: <a href="BitTorrent" title="BitTorrent">BitTorrent</a>-Client</li>

<li><a href="RetroShare" title="RetroShare">RetroShare</a>: serverloser Instant Messenger, anonymes/Filesharing, <a href="Newsgroup" title="Newsgroup">Newsgroup</a>, Voice over IP, E-Mail</li>

<li><a href="RTorrent" title="RTorrent">rTorrent</a>: <a href="BitTorrent" title="BitTorrent">BitTorrent</a>-Client</li>

<li><a href="Tox_(Protokoll)" title="Tox (Protokoll)">Tox</a>: Instant Messenger</li>

<li><a href="Transmission_(Software)" title="Transmission (Software)">Transmission (Software)</a>: <a href="BitTorrent" title="BitTorrent">BitTorrent</a>-Client</li>

<li><a href="YaCy" title="YaCy">YaCy</a>: verteilte <a href="Suchmaschine" title="Suchmaschine">Suchmaschine</a></li></ul>

<div class="mw-heading mw-heading3"><h3 id="DHT-Forschung">DHT-Forschung</h3></div>

<ul><li><span style="display:none"><a rel="nofollow" class="external text" href="http://deadurl.invalid/http://iris.csail.mit.edu/">@1</a></span><span style="display:none"><a rel="nofollow" class="external text" href="http://iris.csail.mit.edu/">@2</a></span><span style="display:none">Vorlage:Toter Link/iris.csail.mit.edu</span><a rel="nofollow" class="external text" href="http://iris.csail.mit.edu/">Project IRIS</a> <small>(Seite nicht mehr abrufbar, festgestellt im November 2017. <a rel="nofollow" class="external text" href="http://timetravel.mementoweb.org/list/2010/http://iris.csail.mit.edu/">Suche in Webarchiven</a>)</small> (Infrastructure for Resilient Internet Systems)</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Einzelnachweise">Einzelnachweise</h2></div>

<li id="cite_note-1"><span class="mw-cite-backlink"><a href="#cite_ref-1">↑</a></span> <span class="reference-text">Agostino Forestiero, Emilio Leonardi, Carlo Mastroianni, Michela Meo: <cite class="lang" lang="en" dir="auto" style="font-style:italic">Self-Chord: A Bio-Inspired P2P Framework for Self-Organizing Distributed Systems</cite>. In: <cite class="lang" lang="en" dir="auto" style="font-style:italic">IEEE/ACM Transactions on Networking</cite>. 18. Jahrgang, <span style="white-space:nowrap">Nr.<span style="display:inline-block;width:.2em"> </span>5</span>, Oktober 2010, <span style="white-space:nowrap">S.<span style="display:inline-block;width:.2em"> </span>1651–1664</span>, <a href="Digital_Object_Identifier" title="Digital Object Identifier">doi</a>:<span class="uri-handle" style="white-space:nowrap"><a rel="nofollow" class="external text" href="https://doi.org/10.1109/TNET.2010.2046745">10.1109/TNET.2010.2046745</a></span> (englisch, <a rel="nofollow" class="external text" href="http://porto.polito.it/2370172/">polito.it</a>).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rfr_id=info:sid/de.wikipedia.org:Verteilte+Hashtabelle&rft.atitle=Self-Chord%3A+A+Bio-Inspired+P2P+Framework+for+Self-Organizing+Distributed+Systems&rft.au=Agostino%26%2332%3BForestiero%2C%26%2332%3BEmilio%26%2332%3BLeonardi%2C%26%2332%3BCarlo%26%2332%3BMastroianni%2C+...&rft.date=2010-10&rft.doi=10.1109%2FTNET.2010.2046745&rft.genre=journal&rft.issue=5&rft.jtitle=IEEE%2FACM+Transactions+on+Networking&rft.pages=1651-1664&rft.volume=18.+Jahrgang" style="display:none"> </span></span>

</li>

<li id="cite_note-2"><span class="mw-cite-backlink"><a href="#cite_ref-2">↑</a></span> <span class="reference-text"><span class="book">Sarunas Girdzijauskas: <cite class="lang" lang="en" dir="auto" style="font-style:italic">Designing peer-to-peer overlays a small-world perspective</cite>. EPFL, 2009 (englisch, <a rel="nofollow" class="external text" href="https://infoscience.epfl.ch/record/130838?ln=en">epfl.ch</a>).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:Verteilte+Hashtabelle&rft.au=Sarunas+Girdzijauskas&rft.btitle=Designing+peer-to-peer+overlays+a+small-world+perspective&rft.date=2009&rft.genre=book&rft.pub=EPFL" style="display:none"> </span></span></span>

</li>

<li id="cite_note-3"><span class="mw-cite-backlink"><a href="#cite_ref-3">↑</a></span> <span class="reference-text"><span class="cite"><a rel="nofollow" class="external text" href="https://web.archive.org/web/20120217054532/http://maite71.upc.es/grup_de_grafs/table_g.html/"><i>The (Degree,Diameter) Problem for Graphs.</i></a> Maite71.upc.es, archiviert vom <style data-mw-deduplicate="TemplateStyles:r250917974">

/* start https://de.wikipedia.org/ */

.mw-parser-output .dewiki-iconexternal>a{background-position:center right!important;background-repeat:no-repeat!important}body.skin-minerva .mw-parser-output .dewiki-iconexternal>a{background-image:url("./_mw_/OOjs_UI_icon_external-link-ltr-progressive.svg")!important;background-size:10px!important;padding-right:13px!important}body.skin-timeless .mw-parser-output .dewiki-iconexternal>a,body.skin-monobook .mw-parser-output .dewiki-iconexternal>a{background-image:url("./_mw_/MediaWiki_external_link_icon.svg")!important;padding-right:13px!important}body.skin-vector .mw-parser-output .dewiki-iconexternal>a{background-image:url("./_mw_/Link.ernal-small-ltr-progressive.svg")!important;background-size:0.857em!important;padding-right:1em!important}

/* end https://de.wikipedia.org/ */

</style><span class="dewiki-iconexternal"><a class="external text" href="https://redirecter.toolforge.org/?url=http%3A%2F%2Fmaite71.upc.es%2Fgrup_de_grafs%2Ftable_g.html">Original</a></span> am <span style="white-space:nowrap;">17. Februar 2012</span><span>;</span><span class="Abrufdatum"> abgerufen am 10. Januar 2012</span> (englisch).</span><span style="display: none;" class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Adc&rfr_id=info%3Asid%2Fde.wikipedia.org%3AVerteilte+Hashtabelle&rft.title=The+%28Degree%2CDiameter%29+Problem+for+Graphs&rft.description=The+%28Degree%2CDiameter%29+Problem+for+Graphs&rft.identifier=https%3A%2F%2Fweb.archive.org%2Fweb%2F20120217054532%2Fhttp%3A%2F%2Fmaite71.upc.es%2Fgrup_de_grafs%2Ftable_g.html%2F&rft.publisher=Maite71.upc.es&rft.date=&rft.source=http://maite71.upc.es/grup_de_grafs/table_g.html&rft.language=en"> </span></span>

</li>

<li id="cite_note-4"><span class="mw-cite-backlink"><a href="#cite_ref-4">↑</a></span> <span class="reference-text">Gurmeet Singh Manku, Moni Naor, Udi Wieder: <a rel="nofollow" class="external text" href="http://citeseer.ist.psu.edu/naor04know.html">"Know thy Neighbor's Neighbor: the Power of Lookahead in Randomized P2P Networks"</a>. Proc. STOC, 2004.</span>

</li>

<li id="cite_note-5"><span class="mw-cite-backlink"><a href="#cite_ref-5">↑</a></span> <span class="reference-text">Ali Ghodsi: <style data-mw-deduplicate="TemplateStyles:r261891140">

/* start https://de.wikipedia.org/ */

.mw-parser-output .webarchiv-memento a{color:inherit}

/* end https://de.wikipedia.org/ */

</style><a rel="nofollow" class="external text" href="https://web.archive.org/web/20070522060750/http://www.sics.se/~ali/thesis/">Distributed k-ary System: Algorithms for Distributed Hash Tables</a> (<span class="webarchiv-memento"><a href="Webarchivierung#Begrifflichkeiten" title="Webarchivierung">Memento</a></span> vom 22. Mai 2007 im <i><a href="Internet_Archive" title="Internet Archive">Internet Archive</a></i>). KTH – Royal Institute of Technology, 2006.</span>

</li>

<li id="cite_note-6"><span class="mw-cite-backlink"><a href="#cite_ref-6">↑</a></span> <span class="reference-text">Miguel Castro, Manuel Costa, Antony Rowstron: <cite class="lang" lang="en" dir="auto" style="font-style:italic">Should we build Gnutella on a structured overlay?</cite> In: <cite class="lang" lang="en" dir="auto" style="font-style:italic">ACM SIGCOMM Computer Communication Review</cite>. 34. Jahrgang, <span style="white-space:nowrap">Nr.<span style="display:inline-block;width:.2em"> </span>1</span>, 1. Januar 2004, <span style="white-space:nowrap">S.<span style="display:inline-block;width:.2em"> </span>131</span>, <a href="Digital_Object_Identifier" title="Digital Object Identifier">doi</a>:<span class="uri-handle" style="white-space:nowrap"><a rel="nofollow" class="external text" href="https://doi.org/10.1145/972374.972397">10.1145/972374.972397</a></span> (englisch, <a rel="nofollow" class="external text" href="http://nms.lcs.mit.edu/HotNets-II/papers/structella.pdf">mit.edu</a> [PDF]).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rfr_id=info:sid/de.wikipedia.org:Verteilte+Hashtabelle&rft.atitle=Should+we+build+Gnutella+on+a+structured+overlay%3F&rft.au=Miguel%26%2332%3BCastro%2C%26%2332%3BManuel%26%2332%3BCosta%2C%26%2332%3BAntony%26%2332%3BRowstron&rft.date=2004-01-01&rft.doi=10.1145%2F972374.972397&rft.genre=journal&rft.issue=1&rft.jtitle=ACM+SIGCOMM+Computer+Communication+Review&rft.pages=131&rft.volume=34.+Jahrgang" style="display:none"> </span></span>

</li>

<li id="cite_note-7"><span class="mw-cite-backlink"><a href="#cite_ref-7">↑</a></span> <span class="reference-text">Domenico Talia, Paolo Trunfio: <cite class="lang" lang="en" dir="auto" style="font-style:italic">Enabling Dynamic Querying over Distributed Hash Tables</cite>. In: <cite class="lang" lang="en" dir="auto" style="font-style:italic">Journal of Parallel and Distributed Computing</cite>. 70. Jahrgang, <span style="white-space:nowrap">Nr.<span style="display:inline-block;width:.2em"> </span>12</span>, Dezember 2010, <span style="white-space:nowrap">S.<span style="display:inline-block;width:.2em"> </span>1254–1265</span>, <a href="Digital_Object_Identifier" title="Digital Object Identifier">doi</a>:<span class="uri-handle" style="white-space:nowrap"><a rel="nofollow" class="external text" href="https://doi.org/10.1016/j.jpdc.2010.08.012">10.1016/j.jpdc.2010.08.012</a></span> (englisch).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rfr_id=info:sid/de.wikipedia.org:Verteilte+Hashtabelle&rft.atitle=Enabling+Dynamic+Querying+over+Distributed+Hash+Tables&rft.au=Domenico%26%2332%3BTalia%2C%26%2332%3BPaolo%26%2332%3BTrunfio&rft.date=2010-12&rft.doi=10.1016%2Fj.jpdc.2010.08.012&rft.genre=journal&rft.issue=12&rft.jtitle=Journal+of+Parallel+and+Distributed+Computing&rft.pages=1254-1265&rft.volume=70.+Jahrgang" style="display:none"> </span></span>

</li>

<li id="cite_note-8"><span class="mw-cite-backlink"><a href="#cite_ref-8">↑</a></span> <span class="reference-text">Peter Sanders, Kurt Mehlhorn, Martin Dietzfelbinger, Roman Dementiev: <cite style="font-style:italic">Sequential and Parallel Algorithms and Data Structures</cite>. Springer, <span style="white-space:nowrap">S.<span style="display:inline-block;width:.2em"> </span>135<span style="display:inline-block;width:.2em"> </span>f</span>.<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:Verteilte+Hashtabelle&rft.au=Peter+Sanders%2C+Kurt+Mehlhorn%2C+Martin+Dietzfelbinger%2C+...&rft.btitle=Sequential+and+Parallel+Algorithms+and+Data+Structures&rft.genre=book&rft.pages=135+f.&rft.pub=Springer" style="display:none"> </span></span>

</li>

</ol></div><div><div class="zim-footer">

Dieser Artikel wurde von <a class="external text" title="Zuletzt bearbeitet am 2025-07-28" href="https://de.wikipedia.org/wiki/?title=Verteilte_Hashtabelle&oldid=258356035">Wikipedia</a> herausgegeben. Der Text ist unter <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de">Creative Commons Attribution-Share Alike 4.0</a> verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.

</div>

</div></div>

</div>

</main>

</div>

</body></html>